package org.huawei260.TiKu.ODsuanfa;

/**
 * @Author: qingle
 * @Date: 2024/10/28-16:11
 * @Description: 3130 【贪心】2024D-在规定时间内获得的最大报酬
 * @version: 1.0
 */
import java.util.Scanner;
public class D_2024D_3130__贪心_在规定时间内获得的最大报酬 {

//	public class Main {
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);

			int T = sc.nextInt();
			int n = sc.nextInt();

			int[][] tws = new int[n + 1][2];
			for (int i = 1; i <= n; i++) {
				tws[i][0] = sc.nextInt();
				tws[i][1] = sc.nextInt();
			}

			System.out.println(getResult(n, T, tws));
		}

		/**
		 * @param T 工作时长
		 * @param tws 数组，元素是tw，也是数组，含义为[该工作消耗的时长, 该项工作的报酬]
		 * @return 最大报酬
		 */
		public static int getResult(int n, int T, int[][] tws) {
			int[][] dp = new int[n + 1][T + 1];

			for (int i = 1; i <= n; i++) {
				int t = tws[i][0]; // 要选择的工作的[时长]
				int w = tws[i][1]; // 要选择的工作的[价值]
				for (int j = 1; j <= T; j++) {
					// 注意这里j不能从t开始，会遗漏处理j < t的情况
					if (j < t) {
						dp[i][j] = dp[i - 1][j];
					} else {
						dp[i][j] = Math.max(dp[i - 1][j], w + dp[i - 1][j - t]);
					}
				}
			}

			return dp[n][T];
		}
	}